package com.astronomia.wheels.leet_code;

import com.astronomia.wheels.array.ArrayUtils;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/*
给定一个整数数组 nums[] 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
   给定 nums = [2, 7, 11, 15], target = 9
   因为 nums[0] + nums[1] = 2 + 7 = 9
   所以返回 [0, 1]
*/
public class 两数之和 {

    private static Integer[] nums = new Integer[]{8, 2, 5, 4, 63, 11, 3, 7, 26, 7, 9, 2, 42, 15, 21, 34};

    private static final int TARGET = 32;

    public static void main(String[] args) {

        long start = System.currentTimeMillis();
        System.out.println(Arrays.toString(twoSum_1(ArrayUtils.toPrimitive(nums), TARGET)));
        System.out.println("it consumes " +(System.currentTimeMillis() - start) + "ms" + "\n");

        long start2 = System.currentTimeMillis();
        System.out.println(Arrays.toString(twoSum_2(ArrayUtils.toPrimitive(nums), TARGET)));
        System.out.println("it consumes " +(System.currentTimeMillis() - start2) + "ms" + "\n");

        long start3 = System.currentTimeMillis();
        System.out.println(Arrays.toString(twoSum_3(ArrayUtils.toPrimitive(nums), TARGET)));
        System.out.println("it consumes " +(System.currentTimeMillis() - start3) + "ms");

    }


    /**
     * byte数组转化为16进制字符串
     * @param bytes
     * @return
     */
    public static String byteToHexString(byte[] bytes) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < bytes.length; i++) {
            String strHex=Integer.toHexString(bytes[i]);
            if(strHex.length() > 3) {
                sb.append(strHex.substring(6));
            } else {
                if(strHex.length() < 2) {
                    sb.append("0" + strHex);
                } else {
                    sb.append(strHex);
                }
            }
        }
        return sb.toString();
    }


    /**
     * 使用暴力法，遍历数组内的所有元素去尝试。
     * 时间复杂度 O(n2)   空间复杂度O(1)
     * @param nums 传入的数组
     * @param target 目标和
     * @return 两个值得下标
     */
    private static int[] twoSum_1(int[] nums, int target) {

        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if(nums[j] == target - nums[i]){
                    return new int[] {j, i};
                }
            }
        }
        throw new IllegalArgumentException("no solution");
    }

    /**
     * 遍历nums数组， 每个值都判断 map中是否存在 target - nums[i] 的key值
     * 如果不存在，则将 nums[i], i 存入 map中
     * 时间复杂度O(1)
     * @param nums 传入的数组
     * @param target 目标和
     * @return 两个值得下标
     */
    private static int[] twoSum_2(int[] nums, int target){
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])){
                return new int[] {map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("no solution");

    }


    private static int[] twoSum_3(int[] nums, int target){

        int[] index = new int[2];
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])){
                index[0] = i;
                index[1] = map.get(nums[i]);
                return index;
            }
            map.put(target - nums[i], i);
        }
        throw new IllegalArgumentException("no solution");
    }



}
